﻿#pragma once

#include <vector>
#include <bitset>
#include <stdint.h>
#include <iostream>
#include <set>
#include <list>
#include <map>
#include <unordered_map>
#include "vector3.h"

class FieldData
{
public:
    using Segment = std::pair<float, float>;
    using SegmentList = std::vector<Segment>;
    using Key = int32_t;
    using Info = std::map<Key, SegmentList>;
public:
    // TODO
    void Init(int32_t A, float a = 1.0f)
    {
        a_ = a;
        filled_field_.resize(A);
    }
public:
    inline std::size_t Height() const
    {
        return filled_field_.size();
    }
    inline bool CheckValid(int32_t v) const
    {
        return 0 <= v && v < static_cast<int32_t>(filled_field_.size());
    }
    inline int32_t ToSlot(float v) const
    {
        return static_cast<int32_t>(v / a_);
    }
    inline float ToReal(int32_t v) const
    {
        return static_cast<float>(v * a_);
    }
    void Fill(int32_t y, Key key, float x1, float x2);
    inline bool Remove(Key key)
    {
        for (auto &it: filled_field_)
        {
            it.erase(key);
        }
        return true;
    }
public:
    void DebugPrint();
public:
    float a_{ 1.0f };
    std::vector<Info> filled_field_;
};

class PolygonQueryImpl
{
public:
    PolygonQueryImpl() = default;
    virtual ~PolygonQueryImpl() = default;
protected:
    using Data = FieldData;
    using SegmentList = Data::SegmentList;
    using Segment = Data::Segment;
    using Point = Vector3;
public:
    virtual bool Query(const Data &data, const Point &point, Point &closet_point) const = 0;
};


class PolygonFillImpl
{
public:
    PolygonFillImpl() = default;
    virtual ~PolygonFillImpl() = default;
protected:
    using Data = FieldData;
    using Point = Vector3;
    using Polygon = std::vector<Point>;
public:
    virtual bool Fill(const Polygon &polygon, Data &data) const = 0;
    virtual bool Fill(const Point &center, float r1, float r2, Data &data) const = 0;
};

/// 种子填充算法
// class PolygonFillSeedImpl : public PolygonFillImpl
// {
// public:
//     virtual bool Fill(const Polygon &polygon, FieldData &data) const override { return false; }
//     virtual bool Fill(const Point &center, float radius, FieldData &data) const override { return false; }
// };

/// 边标志填充算法
// class PolygonFillEdgeImpl : public PolygonFillImpl
// {
// public:
//     virtual bool Fill(const Polygon &polygon, Data &data) const override { return false; }
//     virtual bool Fill(const Point &center, float r1, float r2, Data &data) const override { return false; }
// };

/// 扫描线算法
class PolygonFillSweepLineImpl : public PolygonFillImpl
{
protected:
    struct Line
    {
        float x_left{ 0 };
        float x_delta{ 0 };
        int32_t y_max{ 0 };
        Line(float x_l, float x_d, int32_t y_m) 
        : x_left(x_l), x_delta(x_d), y_max(y_m) {}
    };
    using Lines = std::list<Line>;
    using LinesWithY = std::vector<std::list<Line>>;
protected:
    // inline int32_t ToInteger(float y) const { return static_cast<int32_t>(y); }
    bool GetMinMaxY(const Polygon &polygon, const Data &data, int32_t &y_min, int32_t &y_max) const ;
    void InitEdge(const Data &data, int32_t y_min, const Point &p1, const Point &p2, LinesWithY &lines) const ;
    void InitEdges(int32_t y_min, const Polygon &polygon, const Data &data, LinesWithY &lines) const;
    void InsertAET(const Lines &lines, Lines &aet) const;
    void DoFill(int32_t y, const Lines &aet, Data &data) const;
    void RemoveAET(float y, Lines &aet) const;
    void UpdateAET(Lines &lines) const;
public:
    /// 多边形
    virtual bool Fill(const Polygon &polygon, Data &data) const override;
    /// 圆及圆环
    virtual bool Fill(const Point &center, float r1, float r2, Data &data) const override;
};

/// 查询
class PolygonQuerySegmentImpl : public PolygonQueryImpl
{
protected:
    using Data = FieldData;
    using SegmentList = Data::SegmentList;
    using Segment = Data::Segment;
    using Point = Vector3;
public:
    virtual bool Query(const Data &data, const Point &point, Point &closet_point) const override;
private:
    void MergeSegment(const SegmentList &segment_list, SegmentList &result) const;
    bool IsSegCross(const Segment &s1, const Segment &s2) const;
    bool IsSegContain(const Segment &s1, const Segment &s2) const;
};